# LeetCode 57.插入区间
# https://leetcode.cn/problems/insert-interval/description/

from typing import List
import bisect

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        intervals_left = [interval[0] for interval in intervals]
        intervals_right = [interval[1] for interval in intervals]
        newinterval_left_insert_index = bisect.bisect_left(intervals_right, newInterval[0])
        newinterval_right_insert_index = bisect.bisect_right(intervals_left, newInterval[1])

        result = intervals[: newinterval_left_insert_index]
        if newinterval_left_insert_index == newinterval_right_insert_index:
            result.append(newInterval)
        else:
            sub_ = []
            if newInterval[0] <= intervals[newinterval_left_insert_index][0]:
                sub_.append(newInterval[0])
            else:
                sub_.append(intervals[newinterval_left_insert_index][0])

            if newInterval[1] <= intervals[newinterval_right_insert_index - 1][1]:
                sub_.append(intervals[newinterval_right_insert_index - 1][1])
            else:
                sub_.append(newInterval[1])
            result.append(sub_)
        result.extend(intervals[newinterval_right_insert_index:])

        return result




if __name__ == '__main__':
    # intervals = [[1,3],[6,9]]
    # newInterval = [2,5]

    # intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]
    # newInterval = [4, 8]
    #
    # intervals = []
    # newInterval = [5, 7]

    # intervals = [[1, 5]]
    # newInterval = [2, 3]

    # intervals = [[1, 5]]
    # newInterval = [2, 7]

    intervals =[[1, 5]]
    newInterval =[6, 8]
    result = Solution().insert(intervals, newInterval)
    print(result)
